[Coding039] LeetCode 203

Remove Linked List Elements

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• 虽然并不是每道链表题目都是需要dummy伪结点，但是每道链表的处理都是需要链表的衔接。

  • 链表的衔接很重要，一定要记得，正在处理的结点前面的那个结点有个指针指着它！

• 这道题的第3个代码最佳！

  • 注意p和q两个“指针”的改变时机。

题目：203. Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,2,6,3,4,5,6], val = 6
2
Output: [1,2,3,4,5]

Example 2:

xxxxxxxxxx
2
1
Input: head = [], val = 1
2
Output: []

Example 3:

xxxxxxxxxx
2
1
Input: head = [7,7,7,7], val = 7
2
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 104].

• 1 <= Node.val <= 50

• 0 <= val <= 50

代码1

xxxxxxxxxx
57
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeElements(ListNode head, int val) {
13

14
        if (head == null) return null;
15
        if (head.next == null && head.val == val) return null;
16

17
        // [1,1,1,2] val=1
18
        // [7,7,7,7] val=7
19
        while (head.val == val && head.next != null)
20
        {
21
            head = head.next;
22
        }
23

24
        ListNode dummy = new ListNode(0);
25
        dummy.next = head;
26

27

28
        ListNode p = dummy;
29
        while (p.next != null)
30
        {
31
            ListNode q = p.next;
32
            if (q.val != val)
33
            {
34
                p = q;
35
            }
36
            else
37
            {
38
                while (q.val == val && q.next != null)
39
                {
40
                    q = q.next;
41
                }
42

43
                // [1,2,1] 2
44
                if (q.val == val && q.next == null)
45
                {
46
                    p.next = q.next;
47
                }
48
                else
49
                {
50
                    p.next = q;
51
                }
52
            }
53
        }
54

55
        return dummy.next;
56
    }
57
}

代码解读 | 评价

这个代码显然太复杂了！

复杂度分析

代码2

xxxxxxxxxx
43
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeElements(ListNode head, int val) {
13

14
        if (head == null) return null;
15
        if (head.next == null && head.val == val) return null;
16

17
        // [1,1,1,2] val=1
18
        // [7,7,7,7] val=7
19
        while (head.val == val && head.next != null)
20
        {
21
            head = head.next;
22
        }
23

24
        ListNode dummy = new ListNode(0);
25
        dummy.next = head;
26

27
        ListNode p = dummy;
28
        while (p.next != null)
29
        {
30
            ListNode q = p.next;
31
            if (q.val == val)
32
            {
33
                p.next = q.next;
34
            }
35
            else
36
            {
37
                p = q;
38
            }
39
        }
40

41
        return dummy.next;
42
    }
43
}

代码3（配 · 手绘过程图）※

xxxxxxxxxx
41
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeElements(ListNode head, int val) {
13

14
        while (head != null && head.val == val)
15
        {
16
            head = head.next;
17
        }
18

19
        if (head == null)
20
            return null;
21

22
        ListNode p = head;
23
        ListNode q = head.next;
24

25
        while(q != null)
26
        {
27

28
            if (q.val == val)
29
            {
30
                p.next = q.next;  // p没有动，但删除了q这个节点
31
            }
32
            else
33
            {
34
                p = q;  // p后移一位
35
            }
36

37
            q = q.next;
38
        }
39
        return head;
40
    }
41
}

复杂度分析

代码4

xxxxxxxxxx
69
1
#include<iostream>
2
using namespace std;
3

4
struct ListNode{
5
    int val;
6
    ListNode *next;
7
    ListNode(int x): val(x),next(NULL){}
8
};
9

10
class Solution{
11
    public:
12
        ListNode* removeElement(ListNode* head, int val){
13
            ListNode *p, *q;
14
            ListNode *k;
15
            
16
            
17
            while(head && head->val == val)  // 先把head定下来，如果head==val, head->next == val; 持续删除，定下head
18
            {
19
                head = head->next;
20
            }
21
            
22
            if(!head) return NULL; //删完之后，如果head为空，返回NULL。 或者是 head一开始就为空也返回NULL
23
                        
24
            p = head;
25
            q = head->next;
26
            while(q) // head已经检查过了，不是NULL， 现在看 q (head->next) 
27
            {
28
                if(q->val == val)
29
                {
30
                    p->next = q->next;
31
                }
32
                else // 这个else要注意，目的是为了保证q的前面有个指针，不会让这个链表断开的意思！
33
                {
34
                    p = q;
35
                }
36
                q = q->next;
37
            }
38
            
39
            return head;
40
        }
41
};
42

43
int main()
44
{
45
    ListNode l1(1);
46
    ListNode l2(2);
47
    ListNode l3(6);
48
    ListNode l4(3);
49
    ListNode l5(4);
50
    ListNode l6(5);
51
    ListNode l7(6);
52
    
53
    l1.next = &l2;
54
    l2.next = &l3;
55
    l3.next = &l4;
56
    l4.next = &l5;
57
    l5.next = &l6;
58
    l6.next = &l7;
59
    
60
    Solution sol;
61
    ListNode *res = sol.removeElement(&l1,6);
62
    while(res)
63
    {
64
        cout<<res->val<<" ";
65
        res = res->next;
66
    }
67
    cout<<endl;
68
    return 0;    
69
}

★ 测试样例

• [1,2,6,3,4,5,6] 6

• [] 1

• [7,7,7,7] 7

• [1,2] 1

• [1,2,1] 2

• [2,1] 2